/*
1011. 在 D 天内送达包裹的能力
https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/description/?envType=problem-list-v2&envId=binary-search
难度：中等  李佳韵 2024/09/19
二分查找
*/

#include <bits/stdc++.h>

using namespace std;
class Solution {
public:
    // 检查给定容量是否能在指定天数内运完所有货物
    bool check(vector<int>& weights, int days, int capacity) {
        int dayCount = 1; // 当前使用的天数计数
        int currentLoad = 0; // 当前船的负载
        for (int weight : weights) {
            // 如果当前货物加上船的负载超过容量
            if (currentLoad + weight > capacity) {
                dayCount++; // 需要多一天运输
                currentLoad = weight; // 新的一天，新的负载从当前货物开始
                if (dayCount > days) return false; // 如果使用的天数超过给定天数，返回 false
            } else {
                currentLoad += weight; // 当前货物可以加入当前天的运输
            }
        }
        return true;
    }

    // 计算在指定天数内运完货物所需的最小船容量
    int shipWithinDays(vector<int>& weights, int days) {
        int right = accumulate(weights.begin(), weights.end(), 0); // 最大可能的容量，即所有货物重量之和
        int left = *max_element(weights.begin(), weights.end()); // 最小可能的容量，即最重的单个货物重量
        //int left = maxWeight;
        //int right = totalWeight;
        while (left < right) {
            int mid = (left + right) / 2;
            if (check(weights, days, mid)) {
                right = mid; // 如果 mid 容量可行，尝试更小的容量
            } else {
                left = mid + 1; // 如果 mid 容量不可行，尝试更大的容量
            }
        }
        return left;
    }
};

int main() {
    cout << "请输入货物的数量：";
    int n;
    cin >> n;
    vector<int> weights;
    cout << "请输入每个货物的重量：";
    for (int i = 0; i < n; i++) {
        int weight;
        cin >> weight;
        weights.push_back(weight);
    }
    cout << "请输入需要运输的天数：";
    int days;
    cin >> days;
    Solution solution;
    int result = solution.shipWithinDays(weights, days);
    cout << "在 " << days << " 天内运完所有货物所需的最小船容量为：" << result << endl;
    return 0;
}